闲话

这场一个小时四十分钟做完D的就有200名了.不过感觉我VP的时候还是差了一点,CD都差那么一点,key idea也想了个大半.

A. Prime Subtraction

题目大意:给定两个整数$x$和$y$.保证$x$比$y$大.问两者的差是否可以表示成一个质数$p$的若干倍的形式.

思路

一开始看错题了以为是幂,结果只是和.简单讨论一下就行了:
①如果差为偶数显然$p=2$就满足了
②如果差为奇数且为$1$,无解.
③如果差为奇数且不是$1$,必然有解:因为他要么是一个质数,要么是一个合数,一个质数一定是$1$乘自身,一个合数一定是若干个质因数相乘,因此一定有解.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		ll y,x;scanf("%lld%lld",&x,&y);
		ll sub = x - y;
		if(sub % 2 == 0)	puts("YES");
		else if(sub == 1)	puts("NO");
		else puts("YES");
    }
    return 0;
}

B. Kill 'Em All

题目大意:坐标轴分成两边,以$0$为界限.$\leq 0$的部分是陷阱,$> 0$的部分是怪物的据点.给出$n$个怪物的坐标.你手上有一把武器,他每次可以指定一个位置发射一个炮弹造成一次爆炸,若炮弹的落点坐标是$c$对于在$x$位置上的怪物而言,在爆炸后有三种情况:
①$x=c$,则死亡.
②$x<c$,往左边移动$r$单位.
③$x>c$,往右边移动$r$单位.
注意一次爆炸是没有覆盖范围的,所有敌人都会被影响.
如果一个怪物坐标达到$0$或以下,则会被陷阱杀死.怪物不会自行移动,问你最少要发射几枚炮弹才能消灭所有的敌人,只需输出数量,不需要输出具体方案.

数据范围:
$1 \leq n,r \leq 10^5$
$1 \leq x_i \leq 10^5$

思路

显然要考虑的之后最右边的敌人是否被杀死了.对于每次发射而言,如果把一个怪物推向右边则毫无意义,如果放在最后一个怪物右边,不如放在最后一个怪物身上,因为这一定会炸死最后一个怪物,如果不放的话不一定会杀死最后一个怪物.
因此整个算法流程就非常明显了,就是每次选最后一个怪物,直接炸死他,让前一个成为新的坐标最靠右的,看他是不是已经死了就可以了.不过影响是累加的,所以除了让坐标减少$r$之外,还要额外记录之前炸了多远.简单维护一下就可以.
另外由于坐标可能有重复,所以先去个重,避免讨论重复的问题.以及这个范围还是很大的,注意防范爆int.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 1e5+7;
signed main()
{
    int T;scanf("%lld",&T);
    while(T--)
    {
		int n,r;scanf("%lld%lld",&n,&r);
		vector<int> pos;
		for(int i = 1,x;i <= n;++i)	scanf("%lld",&x),pos.push_back(x);
		sort(pos.begin(),pos.end());
		pos.erase(unique(pos.begin(),pos.end()),pos.end());
		int res = 0,tot = 0;
		while(pos.size() && pos.back() > 0)
		{
			pos.pop_back();
			if(!pos.empty())	pos.back() -= r + tot;
			tot += r;
			++res;
		}
		printf("%lld\n",res);
    }
    return 0;
}

C. Standard Free2play

原题大意:你开始在$h$高的悬崖上,悬崖侧边每一个单位剧里都有一个台阶,开始只有$n$个被打开.数据默认$h$高的台阶是打开的,只有被打开的台阶才可以站上去.如果站在$x$高的台阶上(这个时候$x$必须是打开的),你不能直接跳下去,只能变换$x$的状态为关闭并落下,关闭的同时,$x-1$的状态也会变化一次.你不能跌落超过两个单位高的高度,即从$x$跌落到$x-2$是可以的,但是$x$到$x-3$是不行的.游戏到$0$的时候结束,为了保证你能到$0$,允许你在游戏过程中开挂,任意改变一个位置的板子的状态.问你最少要开几次挂才能完成游戏,只需输出结果而不需要输出方案.

数据范围:
$1 \leq h \leq 10^9$
$1 \leq n \leq\min(h,2*10^5)$
初始打开的$n$个板子以坐标的形式给出.

思路

观察复杂度可以看出来,这个题要么是二分答案去写一个$check$,要么是一个单纯的贪心,因为复杂度不可能直接跟$h$有关,最多也就是$\log(h)$.经过分析之后发现$check$不那么好写,考虑后者.
如果现在是$h$位置,如果下一个板子的高度不比现在的高度高,就跳过.直到有一个平台的高度是比他低的位置,显然高度这次之后会直接到$p_i + 1$,就是这块板子的下一个位置,接下来需要一定的分情况讨论了:首先我是从$p_i$的前面一个位置下来的,我是把$p_i$之前的一个板子状态反转导致$p_i$翻转了才下来的,这个时候,如果$p_{i+1}$是连续的,也就是$p_i = p_{i+1}+1$的话,我可以直接下来到$p_{i+1}$上,否则就必须开挂,并且高度不能落在$p_{i+1}$上而是$p_i$上.之后注意前后的关系模拟就可以了.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+7;
int a[N],f[N];
int main()
{
    int T;scanf("%d",&T);
    while(T--)
    {
		int h,n;scanf("%d%d",&h,&n);
		for(int i = 1;i <= n;++i)	scanf("%d",&a[i]);
		int res = 0;
		for(int i = 2;i <= n;++i)
		{
			if(h <= a[i])	continue;
			h = a[i] + 1;
			if(i < n)
			{
				if(a[i + 1] == a[i] - 1)	h = a[i + 1];
				else ++res,h = a[i];
			}
			else if(h > 2)	++res;
		}
		printf("%d\n",res);
    }
    return 0;
}

D. AB-string

题目大意:一个字符串定义是牛逼的,当且仅当他所有的字符都属于一个连续的回文子串,并且这个回文子串的长度要$>1$.给定一个字符串$s$,计算他有多少个子串是牛逼的.输出结果即可.

数据范围:
$1 \leq 3*10^5$
字符串$s$中只包含有A或B

思路

对于一整个串来说,他一共有$\frac{n*(n-1)}{2}$个子串,从里面挖掉不合法的串就是答案了.考虑什么样的串才是不合法的:显然当一个A和一个B单独的在一起的时候是不合法的,进而形如ABBBB的也肯定不合法.于是可以推出这个题的结论:当子串形如ABBBB,AAAAB,BBBBA,AAAAB的时候这样的串是不合法的.从每一个位置出发往两边找就可以了,每有一个就记录一个.
不过这个题还没完,这样打上去会发现样例的答案偏小,如果偏小意味着不牛逼的子串的数量多了,模拟一下样例之后可以发现是因为AB或BA这样的形式会被算进不牛逼的子串额外一次,最后多做一次遍历就可以解决这个问题了.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5+7;
char s[N];
int main()
{
	int n;scanf("%d",&n);
	ll res = 1ll*n * (n - 1) / 2,bad = 0;
    scanf("%s",s + 1);
    for(int i = 1;i <= n;++i)
    {
    	if(s[i] == 'A')
    	{
    		for(int j = i - 1;j >= 1;--j)
    		{
    			if(s[j] == 'B')	++bad;
    			else break;
    		}
    		for(int j = i + 1;j <= n;++j)
    		{
    			if(s[j] == 'B')	++bad;
    			else break;
    		}
    	}
    	else if(s[i] == 'B')
    	{
    		for(int j = i - 1;j >= 1;--j)
    		{
    			if(s[j] == 'A')	++bad;
    			else break;
    		}
    		for(int j = i + 1;j <= n;++j)
    		{
    			if(s[j] == 'A')	++bad;
    			else break;
    		}
    	}
    }
    for(int i = 1;i <= n - 1;++i)	
    	if(s[i] != s[i + 1])
    		--bad;
    printf("%lld\n",res - bad);
    return 0;
}